#define  _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//
//#define offsetof(type, id) (int)&((*((type*)0)).id)
//
//struct D
//{
//	int i;//0
//	char c;//4
//	float f;//8
//	double d;//16
//	short s;//24
//};
//
//int main()
//{
//	printf("%d\n", offsetof(struct D, i));
//	printf("%d\n", offsetof(struct D, c));
//	printf("%d\n", offsetof(struct D, f));
//	printf("%d\n", offsetof(struct D, d));
//	printf("%d\n", offsetof(struct D, s));
//	return 0;
//}

//#define EXCHANGE_BIT(x) ((x&0xaaaaaaaa)>>1)|((x&0x55555555)<<1)
//
//#include <stdio.h>
//int main()
//{
//	int x = 10;
//	printf("%d\n", EXCHANGE_BIT(x));
//	return 0;
//}

//int main()
//{
//	printf("%s %d %s %s\n", __FILE__, __LINE__, __DATE__, __TIME__);
//
//	return 0;
//}

//#define DEBUG_PRINT printf("%s %d %s %s\n", __FILE__, __LINE__, __DATE__, __TIME__)
//
//int main()
//{
//	DEBUG_PRINT;
//	return 0;
//}


void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap >= 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

void SelectSort(int* a, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int min = begin;
		int max = begin;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] > a[max])
				max = i;
			if (a[i] < a[min])
				min = i;
		}
		swap(&a[begin], &a[min]);
		if (begin == max)
			max = min;
		swap(&a[end], &a[max]);
		end--;
		begin++;
	}
}

AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
			child++;
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
			break;
	}
}

void Heapsort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(a) / sizeof(a[0]);
	Heapsort(a, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	
	return 0;
}